FIG. 1 illustrates a longest prefix match processor 100 utilized in accordance with the prior art. The longest prefix match processor 100 includes a search engine 102 to find entries in a forwarding table 104. Each entry in the forwarding table has an associated switch identifier, which represents the next destination (hop) for a network packet.
FIG. 2 illustrates a simplified version of a prior art forwarding table 200. The forwarding table has a prefix column with a set of entries and a next hop column with a designated switch identifier. Each prefix entry is a segment of a network address. The asterisk (*) designates a “do not care” state. If there is no prefix match, then the next hop is designated as switch “A”. It is desirable to obtain a match with the prefix that is longest since this represents the most specific path to the target machine.
FIG. 3 illustrates a packet 300 that is received by a switch 302 with a longest prefix match processor 100. The longest prefix match processor generates a hop to another machine, such as switches A, C or E or machines B, D, F or G.
FIG. 4 illustrates a binary tree or trie 400. The top of the figure illustrates a triangle 400, which is a simplified representation of the trie 400 shown at the bottom of the figure. The trie 400 has different paths represented by 0s and 1s, where a 0 represents a path to the left and a 1 represents a path to the right. Using this technique, any path in the trie can be designated with digital values. The bottom of the trie 400 has four leaf nodes, as shown, which can branch to eight destinations (0) through (7). The path to destination (0) is represented as 000, since three left branches are used to get to this location. The path to destination (3) is represented as 011 since one left branch (0) is followed by two right branches (11). In this way, each path may be specified using binary values. Trie 400 has three layers of nodes and therefore is said to have a stride of three.
FIG. 5 illustrates that the trie 400 may be in an arbitrarily complex hierarchical relationship with many other tries. For example, trie 400 may be considered as level 0 with eight tries beneath it 400_1 through 400_8 at level 1. This trie expansion can proceed for any number of levels, as shown in FIG. 5. Each trie may have a different size. Thus, it can be appreciated that arbitrarily long path expressions may be defined through such a structure.
FIG. 6 illustrates that each node of a trie 600 may have a designated number. In this example, the nodes are numbered 1 through 7, as shown.
FIG. 7 illustrates a scenario where next hop information resides at the dark nodes (nodes 5 and 7). The path to node 5 may be expressed in binary as 01, while the path to node 7 may be expressed in binary as 11. It can be appreciated with reference to FIG. 5 that the node path can traverse multiple levels and the resultant path to a particular node would be expressed with a long binary value.
In view of the foregoing, there is an ongoing need to provide improved techniques for identifying longest prefix matches.